#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define N 20

// 定义元素类型
typedef int ElemType;
// 定义动态数组
typedef struct {
    ElemType *data;
    int length;
} SSTable;

/**
 * 数组初始化（生成随机数）
 * @param ST
 * @param length
 */
void ST_Init(SSTable &ST, int length) {
    ST.length = length;
    ST.data = (ElemType*) malloc(sizeof (ElemType) * length);
    srand(time(NULL));  // 初始化随机种子
    for (int i = 0; i < length; ++i) {
        ST.data[i] = rand() % 100;
    }
}

/**
 * 数组打印
 * @param ST
 */
void ST_Print(SSTable ST) {
    for (int i = 0; i < ST.length; ++i) {
        printf("%3d", ST.data[i]);
    }
    printf("\n");
}


/**
 * 将两个序列归并
 * @param A
 * @param low
 * @param mid
 * @param high
 */
void Merge(ElemType A[], int low, int mid, int high) {
    ElemType B[N];      // 定义一个辅助数组（长度要大于待排序的数组）
    int i, j, k;
    // 将待排序数组暂存如辅助数组中
    for (k = low; k <= high; ++k) {
        B[k] = A[k];
    }
    // 比较两个序列中元素的大小，存入最终结果序列
    for (i = low, j = mid+1, k=low; i <= mid && j <= high; ++k) {
        if (B[i] < B[j]) {
            A[k] = B[i++];          // 先取值再自增
        } else {
            A[k] = B[j++];
        }
    }
    // 比较完成后将可能剩余的元素直接排到序列最后
    while (i <= mid) {
        A[k++] = B[i++];
    }
    while (j <= high) {
        A[k++] = B[j++];
    }
}

/**
 * 归并排序
 * @param ST
 */
void MergeSort(ElemType A[], int low, int high) {
    if (low < high) {   // 结束循环的条件
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A, low, mid, high);
    }
}


/**
 * 读取10个整型数据12 63 58 95 41 35 65  0 38 44，然后通过归并排序，对该组数据进行排序，输出有序结果，每个数的输出占3个空格
 * @return
 */
int main() {

    ElemType A[10] = {12, 63, 58, 95, 41, 35, 65, 0, 38, 44};
    SSTable ST;
    ST_Init(ST, 10);
    memcpy(ST.data, A, sizeof (A));     // 赋值：题干指定数组
//    ST_Print(ST);

    // 归并排序
    MergeSort(ST.data, 0, ST.length-1);
    ST_Print(ST);

    return 0;
}